package acwing_05;
import java.util.*;
import java.io.*;
public class _3_完全背包问题_滚动数组_carl版 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N = 1010;
	static int n,m;// 物品 容积
	static int dp[] = new int[N];
	static int v[] = new int[N];// 体积
	static int w[] = new int[N];//价值
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			v[i] = Integer.parseInt(st.nextToken());
			w[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < n; i++) {  // 物品
			// 从物品对应的体积v[i]开始，对应的体积之前放不了该物品，默认是0不需要遍历
			// 这里是正序遍历，意味着：当前容积如果还能放得下物品i，就会在之前可能放过物品i的基础上继续放i
			// 详细原理可参考b站代码随想录的 01背包问题 完全背包问题 的解说
			// 跟01背包的滚动数组区别只改了一行代码：for(int j = m; j >= v[i]; j--)
			for(int j = v[i]; j <= m; j++) { // 容积
				dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
			}
		}
		 
		// 直接取最后一个元素的价值就是最大价值
		System.out.println(dp[m]);
	}
}
